package gameplaying;

public class SG1760 {

	//这道题就是一个暴力求解
	int MAX = 51;
	int TOTAL = 25002;
	char[][] map = new char[MAX][MAX];
	char[] s = new char[TOTAL];
	
	private boolean judge(int x, int y){
		if (map[x][y + 1] == '0' && map[x + 1][y] == '0'
				&& map[x + 1][y + 1] == '0') {
			return true;
		}
		return false;  
	}
	
	private void change(int x, int y, char c) {
		map[x][y] = c;
		map[x + 1][y] = c;
		map[x][y + 1] = c;
		map[x + 1][y + 1] = c;
	} 
	
	
	int dfs(int N, int M) {
		for (int i = 0; i < N - 1; ++i) {
			for (int j = 0; j < M - 1; ++j) {
				if (map[i][j] == '0' && map[i + 1][j] == '0'
						&& map[i][j + 1] == '0' && map[i + 1][j + 1] == '0') {
					map[i][j] = map[i + 1][j] = map[i][j + 1] = map[i + 1][j + 1] = '1';
					if (dfs(N, M) == 0) {
						map[i][j] = map[i + 1][j] = map[i][j + 1] = map[i + 1][j + 1] = '0';
						return 1;
					}
					map[i][j] = map[i + 1][j] = map[i][j + 1] = map[i + 1][j + 1] = '0';
				}
			}
		}
		return 0; // 最终没有可放为必败局
	}
}
